package com.test.suanfa;

/**
 * 一个数组前两位固定是0,1，从第三位开始，每一位的数字等于前两位的和，求第N位
 * {0,1,1,2,3,5,8,13,21,24,55}
 */
public class 数列 {

    public static void main(String[] args) {
        int v = new 数列().fn3(10);
        System.out.println(v);
        System.out.println(new 数列().fn4(10));
    }

    public int fn4(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        return fn4(x - 1) + fn4(x - 2);
    }

    public int fn3(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        return fn3(x - 1) + fn3(x - 2);
    }

    public int fn2(int x) {
        int[] arr = new int[x + 1];
        // 定义从根节点遍历
        return fn21(arr, x);
    }

    public int fn21(int[] arr, int num) {
        if (num == 0) return 0;
        if (num == 1) return 1;
        if (arr[num] != 0) return arr[num];
        arr[num] = fn21(arr, num - 1) + fn21(arr, num - 2);
        return arr[num];
    }

    public int fn1(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        return fn1(x - 1) + fn1(x - 2);
    }
}
